I. Field of the Invention
The present invention relates generally to data structures for secondary storage of computer data and more specifically to an optimized structure to increase concurrency for readers of data structures.
II. Description of the Prior Art
Modern computer systems are very often used to search for and use specific data that can only be found amongst large amounts of data. The organization of the data and the methods for accessing it are extremely important, since adoption of efficient techniques can significantly increase system performance and throughput.
In many computer software and systems high performance and throughput gains may be obtained through the usage of high degrees of parallelism, i.e having more than one process active at any given time. Within that parallelism it is still necessary that the separate processes not interact with each other in such a way that inconsistent data structures are created. Typically a technique called `locking` is used to assure that no two processes can make a change to the same data structure at the same time. Locking is also used to assure that processes that are reading, but not changing, the data are no longer present. Multiple readers are often permitted in the absence of a writing process.
In practice, readers are seldom operating in the same part of a data structure as the writers. Additionally, pure readers, that is, readers having no intent to update, are usually wear searchers. This is particularly true when the reading process is searching for a single object (e.g. a record) instead of multiple objects that may have an abstract interrelationship.
As is well known to skilled computer programmers and system designers, many techniques for structuring data files have been proposed. The selection of the file organization depends upon the type of file retrieval to be performed. Broadly speaking, there are two types of file retrieval needed, namely sequential and random.
In many common file organization types, there is an index to the data that speeds the searcher by directing it to the part of the file containing the searched for item.
Usually, a unique key is assigned to each item in the file and retrieval is performed by specifying the key. A file may be considered as a set of n records containing the file information and a key that is uniquely associated with the file information. It is assumed that the key uniquely identifies the record.
A user may conduct various types of transactions against a file including the insertion, deletion retrieval and updating of the file records. Four basic operations support these transactions:
1. INSERT: Adds a new record making sure that the key is unique.
2. DELETE: Remove the record indicated by a key.
3. FIND: Retrieves a record indicated by a key.
4. NEXT: Retrieves the next group of information.
Since its introduction by Bayer and McCreight, "Organization and maintenance of large ordered indices," Acta Informatica, vol. 1, pp. 173-189, 1972, the B-tree has become popular as a method for organizing and maintaining large ordered indices of dynamic random-access files. Variants of the original algorithm have been popular. The present invention applies to leaf search B-trees, which is a variant developed by Wedekind, H., "On the selection of access paths in a data base system," in Data Base Management, Klimbie, J. W. and Koffeman, K. L. (Eds.), North-Holland, 1974, pp 385-397, which have been called B+-trees in Comer, D., "The ubiquitous B-tree," ACM Computing Surveys. vol. 11, pp. 121-138, 1979. and B*-trees in Bayer, R. and Unterauer, K., "Prefix B-trees," ACM Trans. on Database Systems. vol. 2, 1 (March 1977), pp. 11-26, and Wedekind. The terminology of Comer, B+-tree, is used in the present description to refer to leaf search B-trees.
It is often desirable that weak searchers of B+-trees not be required to use locks within the B+-tree itself. A weak searcher is a reader with no intent to update. A weak-search returns a result that was valid at some time during the search, but is not guaranteed to be current at the time of search termination. If, however, a weak-searcher has obtained a lock on the object of the search before starting to traverse the B-tree, then, using this invention it will be guaranteed a valid (i.e, current) object at the time of search termination.
Not requiring weak searchers to use locks is especially beneficial if most accesses are by weak searchers, or if a lock on the object of the search is obtained before commencing the search, or in distributed applications where the lock facility may be remote to some subset of the sharing systems. The benefits are increased concurrency and reduced overhead due to lock traffic.
Lehman, P., and Yao, S., "Efficient locking for concurrent operations on B-trees," ACM Trans. on Database Systems, 6, Dec. 1981, pp. 650-670, describes a method that does not require readers to lock called the B-link tree, which does not define methods for the contraction of the B-tree in the traditional manner. Although this might be acceptable in a tree that is either stable or changing with uniformly distributed insertions and deletions, it is not generally robust. In particular, the result of 0.69 mean density, described in Yao, A. "On random 2-3 trees," Acta Inf. 9, 2 (1978), 159-170, will not hold. In addition, the B-link tree is not amenable to the application of shadow update which is used to perform an atomic update involving more than one node.
Typically the process of obtaining a lock is expensive. The presence of readers delays the start time of a writer until the readers have finished, which tends to reduce the parallelism of the system. Systems known in the art have not allowed pure readers to operate without locking.
Accordingly, it is an object of the invention to provide a method for efficiently accessing data structures in parallel systems.
It is a further object of the invention to provide a method that permits weak searchers to operate without requiring locking.
These, and other, objects, advantages, and features of the invention will be more apparent upon reference to the description and the appended drawings.